//
// Created by hay boy on 2022/6/22.
//
#ifndef ALGORITHM_SORT_BINSORT
#define ALGORITHM_SORT_BINSORT
#include <iostream>
#include <string>
#include "../chainNode/ChainNode.h"
using namespace std;
struct StudentRecord{
    int score;
    string* name;
    explicit operator int() const{
        return score;
    }
    bool operator!=(const StudentRecord& x) const{
        return score!=x.score;
    }
};
ostream& operator<<(ostream& out,const StudentRecord& x){
    out<<x.score<<' '<<*x.name<<endl;
    return out;
}
/**
 * 因为后插入到箱子里的被放到链表头部，而取的时候也是从头部开始取，所以这是不稳定的箱子排序。
 * **/
void BinSort(Chain<StudentRecord> &theChain,int range){
    Chain<StudentRecord> *bin;
    bin = new Chain<StudentRecord>[range+1];
    int numberOfElements = theChain.size();
    for(int i = 1;i<=numberOfElements;i++){
        StudentRecord x = theChain.get(0);
        theChain.erase(0);
        bin[x.score].insert(0,x);
    }
    for(int j = range;j>=0;j++){
        while(!bin[j].empty()){
            StudentRecord x = bin[j].get(0);
            bin[j].erase(0);
            theChain.insert(0,x);
        }
    }
    delete[] bin;
}
#endif
